1. Field of the Invention
This invention relates to transport protocols for internetwork routing.
2. Description of Related Art
In a network of coupled devices, or a collection of such networks, message transmission from senders to recipients may be unreliable, i.e., messages that are sent are not guaranteed to be received properly or in order. Because message transmission in a network may be unreliable, known routing methods include techniques for transmitting messages reliably, i.e., in a manner so that messages are sure to arrive at the intended destination and are sure to arrive in order, if delivery is possible at all. Typically, these methods require that messages to be sent reliably must be sent with a sequence number, which the recipient must acknowledge. The recipient may also be required to reorder received messages by sequence number. Reliable transfer protocols are described in R. Perlman, Interconnections, at sections 1.4 and 9.10.2.
One example where reliable message transmission may be preferred is when large blocks of information must be coordinated among several devices, particularly when those large blocks of information may be updated from time to time. One important case where this is generally required is in a collection of networks of coupled devices, in which multiple routers must generally coordinate large blocks of information about the network topology. One method of the prior art is to retransmit the entire block periodically, so that if a message containing a block is lost or misordered, any error introduced by that fact will be redressed with the next transmitted block. While this method achieves the purpose of coordinating multiple devices, it requires a large amount of transmission bandwidth, even when there is no substantial change in network topology.
Another approach to coordinating information among multiple routers is for the routers to send only updates to the information they maintain. This would use substantially less transmission bandwidth, and have the advantage that few messages would be required during periods when the network topology remained substantially unchanged. However, this technique would require that updates be sent reliably, as the undetected loss of an update message would mean that two routers would lose synchronization.
A new routing method called DUAL requires guaranteed and ordered delivery, if delivery is possible at all, of update and other protocol messages. The DUAL method uses reliable delivery to maintain and coordinate a record, among multiple routers, for each possible destination in the collection of networks. One aspect of the DUAL method is the frequent use of multicast transmissions to all neighbors of a particular router.
However, one drawback of the DUAL method, particularly with its frequent use of multicast transmissions, is that it requires each recipient (i.e., each router) to maintain a great deal of state information about receipt and order of protocol packets it receives from each sender (i.e., each neighbor router). For example, each receiver must keep track of what packets it has received, and maintain a set of queues of packets that are received out of order. This greatly complicates operation of each recipient, and is redundant with the same information maintained by each sender. Morevoer, most reliable transmission protocols are connection-oriented, and are thus not suitable for multicast transmissions. It would be advantageous to simply operation of each recipient, for example by maintaining such information only at each sender.
More generally, it would be advantageous to have a method for interspersing multicast and unicast packets, that are to be reliably transmitted, that is simpler and does not require the recipient to maintain information that is redundant with that maintained by the sender. It would also be advantageous to have a method for internetwork routing using multicast and unicast protocol packets, that does not waste transmission bandwidth and does not require routers to maintain excess information.
In a collection of coupled networks, there may be networks or regions of networks that use differing routing protocols. It would be advantageous for routers in one region of the collection of networks to be able to use routing information collected and transmitted by routers in another region, even if those routers use a different routing protocol.
In such a collection of coupled networks, there may be networks with disparate administrative requirements, and it may be desirable to route packets in response to such administrative requirements. For example, it may be desirable for certain packets to be routed entirely within a set of predetermined networks, e.g., for security or policy reasons. It may be desirable for certain packets to be excluded from a set of predetermined networks, e.g., for financial or policy reasons. It may be desirable for certain packets or packets transmitted to certain destinations to receive high priority or low priority, to be routed by the fastest route or the most reliable route. For example, when transmitting sound recordings or when transmitting to certain destinations, it may be desirable for packets to be routed by the method that generates the least delay. It would be advantageous for routers to be able to label destinations that require special routing in response to policy considerations, and to route packets transmitted to those destinations in response to their labels.
Accordingly, it is an object of the invention to provide an improved reliable transport protocol and an improved routing protocol.